//
//  ParallelMinCut.h
//  Min-Cut
//
//  Created by Emanuele Vespa on 5/9/12.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//

#ifndef Min_Cut_ParallelMinCut_h
#define Min_Cut_ParallelMinCut_h



#endif


#include "MultiGraph.h"
#include <tbb/tbb.h>


class compare_cuts {
    
    public:
    
    
    bool operator () (const MultiGraph& g1, const MultiGraph& g2) const {
        
        if( g1.cut_weight < g2.cut_weight) return true;
        else return false;
        
        
    }
    
    
};



class MinCutRun: public tbb::task {
    
    
public:
    
    MultiGraph g;
    tbb::concurrent_priority_queue<MultiGraph, compare_cuts> * q;
    MultiGraph * min_cut;
    MultiGraph * min_cut_partial;
    int partial_minimum;
    int num_runs;
    int task_id;
    
    MinCutRun(MultiGraph& _in, MultiGraph  * _min_cut, int _num_runs, int _task_id, tbb::concurrent_priority_queue<MultiGraph, compare_cuts> * _q) {
        
        g = _in;
        min_cut = _min_cut;
        partial_minimum = 1000000000;
        num_runs = _num_runs;
        task_id = _task_id;
        q = _q;
        
    }
    
    tbb::task* execute() {
        
         
        
//        cout << "Starting " << num_runs << " runs" << endl;
        
        for( int i = 0 ; i < num_runs; i++){
            
            
            MultiGraph * temp = new MultiGraph(g);
            
            temp->randContract();
            
            if( temp->cut_weight < partial_minimum) {
                
                *min_cut = *temp;
                
                partial_minimum = temp->cut_weight;
                
            }
            
            else delete temp;
            
        }
        
        
        
//        cout << "Task " << task_id << " completed" << endl;
//        
//        
//        cout << "The partial min cut weight is : " << min_cut->cut_weight << " processed by thread " << task_id << endl;
//        
        

        
        return NULL;
        
    }
    
    
};



class MinCutRoot : public tbb::task {
        
    
public:
    
    // variables
    MultiGraph &original;
    MultiGraph & global;    
    std::vector<MultiGraph *> partial_min_cuts;
    int num_threads;
    int num_runs;
    
    tbb::task_list list;
    
    tbb::concurrent_priority_queue<MultiGraph, compare_cuts> queue;
    
    // methods
    
    MinCutRoot(MultiGraph &_original, MultiGraph & _global): global(_global), original(_original), queue(){
        
        
        
        num_threads = tbb::task_scheduler_init::default_num_threads();
        num_runs = (original.vertexNum * original.vertexNum) / num_threads;
        
      
        
    }
    
    
    MinCutRoot(MultiGraph &_original, MultiGraph & _global, int _num_threads): global(_global), original(_original), queue(){
        
        
        
        num_threads = _num_threads;
        num_runs = (original.vertexNum * original.vertexNum) / num_threads;
        
        
        
    }

    
    
    tbb::task * execute(){
        
        
        cout << "Root task spawned" << endl;
        
        cout << "Number of child task : " << num_threads << endl;
        
        for (int i = 0 ; i < num_threads; i++) {
            
            partial_min_cuts.push_back( new MultiGraph(original) );
            
//            cout << "Copied graph num " << i << endl;
            
        
            MinCutRun& run = *new ( allocate_child() ) MinCutRun( original, partial_min_cuts[i], num_runs, i, &queue );
            
            list.push_back(run);
            
            
            
        }
        
        
        
        
//        cout << "List created " << endl;
        
        set_ref_count(num_threads+1);
        
        task::spawn_and_wait_for_all(list);
        
        
        
        int min = INT_MAX;
        int min_index;
        
        
        for( int i = 0; i < num_threads; i++ ){
            
            if (partial_min_cuts[i]->cut_weight < min){
                
                min_index = i;
                min = partial_min_cuts[i]->cut_weight;
                
            }
            
        }
        
        global = *partial_min_cuts[min_index];
                    

        
        
        

        
        
        return NULL;
        
    }
    
};


int MultiGraph::ParallelKarger(){
    
    
    
    MultiGraph * min_cut;
    min_cut = new MultiGraph;
    
    
    MinCutRoot& r = * new ( tbb::task::allocate_root()) MinCutRoot(*this, *min_cut);
    
    tbb::task::spawn_root_and_wait(r);
        
    
    
    
}


int MultiGraph::ParallelKarger(int num_threads){
    
    
    
    MultiGraph * min_cut;
    min_cut = new MultiGraph;
    
    
    tbb::task_scheduler_init init(num_threads);
    
    MinCutRoot& r = * new ( tbb::task::allocate_root()) MinCutRoot(*this, *min_cut, num_threads);
    
    tbb::task::spawn_root_and_wait(r);
    
    
    
    
}




